SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Defunctionalization</title>

</head>

Defunctionalization

</h1>

</header>

In <a href="Programming_languages" class="mw-redirect" title="Programming languages">programming languages</a>, defunctionalization is a <a href="Compile_time" title="Compile time">compile-time</a> transformation which eliminates <a href="Higher-order_function" title="Higher-order function">higher-order functions</a>, replacing them by a single first-order apply function. The technique was first described by <a href="John_C._Reynolds" title="John C. Reynolds">John C. Reynolds</a> in his 1972 paper, "Definitional Interpreters for Higher-Order Programming Languages". Reynolds' observation was that a given program contains only finitely many function abstractions, so that each can be assigned and replaced by a unique identifier. Every function application within the program is then replaced by a call to the apply function with the function identifier as the first argument. The apply function's only job is to dispatch on this first argument, and then perform the instructions denoted by the function identifier on the remaining arguments.

One complication to this basic idea is that <a href="Abstraction_(computer_science)" title="Abstraction (computer science)">function abstractions</a> may reference <a href="Free_variables" class="mw-redirect" title="Free variables">free variables</a>. In such situations, defunctionalization must be preceded by <a href="Closure_conversion" class="mw-redirect" title="Closure conversion">closure conversion (lambda lifting)</a>, so that any free variables of a function abstraction are passed as extra arguments to apply. In addition, if <a href="Closure_(computer_science)" class="mw-redirect" title="Closure (computer science)">closures</a> are supported as <a href="First-class_value" class="mw-redirect" title="First-class value">first-class values</a>, it becomes necessary to represent these captured bindings by creating data structures.

Instead of having a single apply function dispatch on all function abstractions in a program, various kinds of <a href="Control_flow_analysis" class="mw-redirect" title="Control flow analysis">control flow analysis</a> (including simple distinctions based on <a href="Arity" title="Arity">arity</a> or <a href="Type_signature" title="Type signature">type signature</a>) can be employed to determine which function(s) may be called at each function application site, and a specialized apply function may be referenced instead. Alternatively, the target language may support indirect calls through <a href="Function_pointer" title="Function pointer">function pointers</a>, which may be more efficient and extensible than a dispatch-based approach.

Besides its use as a compilation technique for higher-order <a href="Functional_languages" class="mw-redirect" title="Functional languages">functional languages</a>, defunctionalization has been studied (particularly by <a href="Olivier_Danvy" title="Olivier Danvy">Olivier Danvy</a> and collaborators) as a way of mechanically transforming <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreters</a> into <a href="Abstract_machine" title="Abstract machine">abstract machines</a>. Defunctionalization is also related to the technique from <a href="Object-oriented_programming" title="Object-oriented programming">object-oriented programming</a> of representing functions by <a href="Function_object" title="Function object">function objects</a> (as an alternative to closures).

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

This is an example given by <a href="Olivier_Danvy" title="Olivier Danvy">Olivier Danvy</a>, translated to Haskell:

Given the Tree datatype:

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre>data Tree a = Leaf a

| Node (Tree a) (Tree a)

</pre></div>

We will defunctionalize the following program:

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre>cons :: a -> [a] -> [a]

cons x xs = x : xs

o :: (b -> c) -> (a -> b) -> a -> c

o f g x = f (g x)

flatten :: Tree t -> [t]

flatten t = walk t []

walk :: Tree t -> [t] -> [t]

walk (Leaf x) = cons x

walk (Node t1 t2) = o (walk t1) (walk t2)

</pre></div>

We defunctionalize by replacing all higher-order functions (in this case, <code>o</code> is the only higher-order function) with a value of the <code>Lam</code> datatype, and instead of calling them directly, we introduce an <code>apply</code> function that interprets the datatype:

<div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre>data Lam a = LamCons a

| LamO (Lam a) (Lam a)

apply :: Lam a -> [a] -> [a]

apply (LamCons x) xs = x : xs

apply (LamO f1 f2) xs = apply f1 (apply f2 xs)

cons_def :: a -> Lam a

cons_def x = LamCons x

o_def :: Lam a -> Lam a -> Lam a

o_def f1 f2 = LamO f1 f2

flatten_def :: Tree t -> [t]

flatten_def t = apply (walk_def t) []

walk_def :: Tree t -> Lam t

walk_def (Leaf x) = cons_def x

walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)

</pre></div>

<ul><li><a href="Closure_conversion" class="mw-redirect" title="Closure conversion">Closure conversion</a></li>

<li><a href="Partial_evaluation" title="Partial evaluation">Partial evaluation</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFReynolds1972" class="citation conference cs1"><a href="John_C._Reynolds" title="John C. Reynolds">Reynolds, John</a> (August 1972). "Definitional Interpreters for Higher-Order Programming Languages". Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717–740. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800194.805852">10.1145/800194.805852</a>.</cite></li>

<li><cite id="CITEREFDanvyNielsen2001" class="citation conference cs1"><a href="Olivier_Danvy" title="Olivier Danvy">Danvy, Olivier</a>; Nielsen, Lasse R. (2001). <a rel="nofollow" class="external text" href="http://www.daimi.au.dk/~danvy/DSc/22_danvy-nielsen_ppdp-2001.pdf">"Defunctionalization at Work"</a> (PDF). Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. pp. 162–174. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F773184.773202">10.1145/773184.773202</a>.</cite> (More comprehensive version: <a rel="nofollow" class="external text" href="http://www.brics.dk/RS/01/23/BRICS-RS-01-23.pdf">Technical Report BRICS-RS-01-23</a>)</li>

<li><cite id="CITEREFDanvyMillikin2009" class="citation journal cs1"><a href="Olivier_Danvy" title="Olivier Danvy">Danvy, Olivier</a>; Millikin, Kevin R. (June 2009). "Refunctionalization at Work". Science of Computer Programming. 74 (8): 534–549. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.scico.2007.10.007">10.1016/j.scico.2007.10.007</a>.</cite> (Also available as <a rel="nofollow" class="external text" href="http://www.brics.dk/RS/07/7/BRICS-RS-07-7.pdf">Technical Report BRICS-RS-07-7</a>)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://spivey.oriel.ox.ac.uk/corner/Defunctionalization_(Programming_Languages)">Defunctionalization (Programming Languages)</a>. Oxford University.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-04-06" href="https://en.wikipedia.org/wiki/?title=Defunctionalization&oldid=1217506827">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>